package hasthi.tools;

import hasthi.common.HasthiException;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class OrderedGrpah<T> {
    private Map<T,Entry> entries = new HashMap<T, Entry>();
    private Map<T,Entry> heads = new HashMap<T, Entry>();
    
    
    public class Entry{
        public Entry(T t){
            this.entry = t;
        }
        private T entry;
        private LinkedList<Entry> entries = new LinkedList<Entry>();
        @Override
        public String toString() {
            return entry.toString();
        }
        
    }
    
    
    public void addPartialOrder(T from,T to){
        Entry frome = entries.get(from);
        Entry toe = entries.get(to);
        if(frome == null){
            frome =  new Entry(from);
            entries.put(from, frome);
            heads.put(from, frome);
        }
        if(toe == null){
            toe =  new Entry(to);
            entries.put(to, toe);
        }
        
        if(heads.containsKey(to)){
            heads.remove(to);
        }
        frome.entries.add(toe);
    }
    /**
     * this is the implementation of the topology sort described in the 
     * http://en.wikipedia.org/wiki/Topological_sort, this uses the second
     * method that uses post order of the DFS
     * @param start
     * @return
     * @throws HasthiException
     */
    public List<T> topologySort(T start) throws HasthiException{
        Entry starte = entries.get(start);
        List<T> sortedList;
        if(starte == null){
            sortedList = new  ArrayList<T>(1);
            sortedList.add(start);
            return sortedList;
        }else{
            sortedList = new ArrayList<T>();    
        }
        Map<Entry,Entry> visited = new HashMap<Entry, Entry>();
        //visited.put(starte, starte);
        topologySort(starte, sortedList, visited);
        
//        while(!stack.isEmpty()){
//            Entry head = stack.pop();
//            System.out.println("pop "+head);
//            if(head.entries.isEmpty() || visited.containsKey(head)){
//                sortedList.add(head.entry);
//            }else{
//                visited.put(head,head);
//                Iterator<Entry> iterator = head.entries.iterator();
//                while(iterator.hasNext()){
//                    Entry e = iterator.next();
//                    if(visited.containsKey(e)){
//                        throw new HasthiException("There are cyclic dependancies found "+e+ " while "+visited ,FaultCode.InvaliedLocalArgumnet);
//                    }
//                    stack.push(e);
//                    System.out.println("push "+e);
//                }
//            }
//        }
        return sortedList;
    }
    
    
    private void topologySort(Entry start,List<T> sortedList,Map<Entry,Entry> visited){
        visited.put(start, start);
        Iterator<Entry> iterator = start.entries.iterator();
        while(iterator.hasNext()){
            Entry e = iterator.next();
            if(!visited.containsKey(e)){
                topologySort(e, sortedList, visited);
            }
        }
        sortedList.add(start.entry);
    }
    
    public static void main(String[] args) throws HasthiException {
        OrderedGrpah<String> grpah = new OrderedGrpah<String>();
        grpah.addPartialOrder("gfac", "xregistry");
        grpah.addPartialOrder("xregistry", "mysql");
        grpah.addPartialOrder("gfac", "mylead");
        grpah.addPartialOrder("gfac", "messanger");
        grpah.addPartialOrder("messanger","mysql");
        grpah.addPartialOrder("mylead", "messanger");
        grpah.addPartialOrder("mylead", "damn");
        grpah.addPartialOrder("damn", "gridftp");
        grpah.addPartialOrder("gfac", "gridftp");
        
        System.out.println(grpah.topologySort("gfac"));
        
        System.out.println(grpah.topologySort("mylead"));
    }
}
